#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;

// 双端队列节点（带前驱和后继指针）
typedef struct DNode {
    ElemType data;
    struct DNode *prior;  // 前驱指针
    struct DNode *next;   // 后继指针
} DNode, *DQueuePtr;

// 双端队列结构体
typedef struct {
    DQueuePtr front;  // 队头指针
    DQueuePtr rear;   // 队尾指针
} Deque;

// 初始化双端队列
Status InitDeque(Deque *Q) {
    Q->front = Q->rear = (DQueuePtr)malloc(sizeof(DNode));
    Q->front->prior = Q->front->next = NULL;  // 头节点（哨兵）
    return OK;
}

// 判断队列是否为空
Status IsEmpty(Deque *Q) {
    return (Q->front == Q->rear) ? OK : ERROR;
}

// 队头入队
Status EnQueueFront(Deque *Q, ElemType e) {
    DQueuePtr p = (DQueuePtr)malloc(sizeof(DNode));
    p->data = e;
    p->next = Q->front->next;  // p的后继是原队头元素
    if (Q->front->next) Q->front->next->prior = p;  // 原队头元素的前驱指向p
    else Q->rear = p;  // 若队空，队尾也指向p
    Q->front->next = p;
    p->prior = Q->front;
    return OK;
}

// 队尾入队
Status EnQueueRear(Deque *Q, ElemType e) {
    DQueuePtr p = (DQueuePtr)malloc(sizeof(DNode));
    p->data = e;
    p->prior = Q->rear;  // p的前驱是原队尾
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;  // 队尾指针更新
    return OK;
}

// 队头出队
Status DeQueueFront(Deque *Q, ElemType *e) {
    if (IsEmpty(Q)) return ERROR;
    DQueuePtr p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (p->next) p->next->prior = Q->front;
    else Q->rear = Q->front;  // 若p是最后一个节点，队尾回退
    free(p);
    return OK;
}

// 队尾出队
Status DeQueueRear(Deque *Q, ElemType *e) {
    if (IsEmpty(Q)) return ERROR;
    DQueuePtr p = Q->rear;
    *e = p->data;
    Q->rear = p->prior;  // 队尾指针前移
    Q->rear->next = NULL;
    free(p);
    return OK;
}

// 打印队列
void PrintDeque(Deque *Q) {
    if (IsEmpty(Q)) {
        printf("双端队列为空\n");
        return;
    }
    printf("双端队列元素：");
    DQueuePtr p = Q->front->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 测试
int main() {
    Deque Q;
    InitDeque(&Q);
    EnQueueRear(&Q, 1);   // 队尾入1 → [1]
    EnQueueFront(&Q, 2);  // 队头入2 → [2,1]
    EnQueueRear(&Q, 3);   // 队尾入3 → [2,1,3]
    PrintDeque(&Q);       // 2 1 3

    int e;
    DeQueueFront(&Q, &e);  // 队头出2 → [1,3]
    DeQueueRear(&Q, &e);   // 队尾出3 → [1]
    PrintDeque(&Q);        // 1
    return 0;
}